//: [Previous](@previous)

/*:
 # 冒泡排序
 * 最好情况 O(n)
 * 最坏情况 O(n^2))
 * 平均时间复杂度 O(n^2))
 * 空间复杂度 0(1)
 
 1. 比较相邻的两个数，如果第一个比第二个大就交换
 2. 重复执行直到最后一个数
 3. 去掉最后一个数，重复1，2步。
 
 */

var numbers = [3, 6, 5, 2, 7, 9, 1, 4, 3]
print("排序前 \(numbers)")

func bubbleSort(_ arr: [Int]) -> [Int] {
    if arr.count < 2 {
        return arr
    }
    
    var nums = arr
    
    for i in 0..<nums.count {
        for j in 0..<nums.count-1-i {
            if nums[j] > nums[j+1] {
                nums.swapAt(j, j+1)
            }
        }
    }
    
    return nums
}

print("冒泡排序后 \(bubbleSort(numbers))")

//: [Next](@next)
